#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <stdbool.h>

#define NNEG(x)	((x) > 0 ? (x) : 0)

// {{{ priority queue
struct prio_queue {
	struct edge	*array;
	int		size;
	int		size_max;
};

#ifndef SWAP_INT
#define SWAP_INT(a, b)	(((a) ^ (b)) && ((b) ^= (a) ^= (b), (a) ^= (b)))
#endif

static void
mem

static void
heap__sift_down(struct prio_queue *pq, int start)
{
	int parent = start,
	    child,
	    swap;

	while (parent * 2 + 1 < pq->size) {
		child = parent * 2 + 1;
		swap = parent;

		if (pq->array[parent].weight > pq->array[child].weight) {
			swap = child;
			#ifdef DEBUG
			fprintf(stderr, "Heap__sift_down(): parent=%d child=%d, swap=%d ; pq->array[parent].weight=%d pq->array[child].weight=%d\n",
					parent, child, swap, pq->array[parent].weight, pq->array[child].weight);
			#endif
		}

		if (child+1 < pq->size &&
		    pq->array[swap].weight > pq->array[child+1].weight)
			swap = child+1;

		if (swap != parent) {
			SWAP_INT(pq->array[parent].a, pq->array[swap].a);
			SWAP_INT(pq->array[parent].b, pq->array[swap].b);
			SWAP_INT(pq->array[parent].weight, pq->array[swap].weight);
			SWAP_INT(pq->array[parent].index, pq->array[swap].index);
			parent = swap;
		} else {
			return;
		}
	}
}

static void
heap__sift_up(struct prio_queue *pq, int start, int end)
{
	register int child = end, parent = (end - 1) / 2;

	/*
	 * 'start' is a kind of left barrier for this function
	 */
        while (child > start)
		if (pq->array[(child - 1) / 2].weight > pq->array[child].weight) {
			SWAP_INT(pq->array[parent].a, pq->array[child].a);
			SWAP_INT(pq->array[parent].b, pq->array[child].b);
			SWAP_INT(pq->array[parent].weight, pq->array[child].weight);
			SWAP_INT(pq->array[parent].index, pq->array[child].index);

			child = parent;
			parent = (child - 1) / 2;
		} else {
			break;
		}
}

static void
heap__heapify(struct prio_queue *pq)
{
	int start = pq->size / 2 - 1;

	while (start >= 0)
		Heap__sift_down(pq, start--);
}

static struct edge
pq_extract_min(struct prio_queue *pq)
{
	SWAP_INT(pq->array[0].a, pq->array[pq->size-1].a);
	SWAP_INT(pq->array[0].b, pq->array[pq->size-1].b);
	SWAP_INT(pq->array[0].weight, pq->array[pq->size-1].weight);
	SWAP_INT(pq->array[0].index, pq->array[pq->size-1].index);
	--pq->size;
	Heap__sift_down(pq, 0);

	return pq->array[pq->size];
}

static void
pq_init(struct prio_queue *pq, const int n)
{
	pq->array = (struct edge *) calloc(8, sizeof *pq->array);
	pq->size = 0;
	pq->size_max = 8;
}

static void
pq_insert(struct prio_queue *pq, const int a_idx, const int b_idx,
		const int weight, const int index)
{
	struct edge *tmp;

	if (pq->size + 1 > pq->size_max) {
		tmp = (struct edge *) realloc(pq->array, (sizeof *tmp) * (pq->size_max *= 2));
		if (tmp == NULL) {
			fprintf(stderr, "failed to realloc pq->array (new size = %d)\n",
					pq->size_max);
			assert(tmp != NULL);
		} else
			pq->array = tmp;
	}

	pq->array[pq->size].a = a_idx;
	pq->array[pq->size].b = b_idx;
	pq->array[pq->size].weight = weight;
	pq->array[pq->size].index  = index;
	if (pq->array[pq->size].a > pq->array[pq->size].b)
		SWAP_INT(pq->array[pq->size].a, pq->array[pq->size].b);
	pq->size += 1;

	Heap__sift_up(pq, 0, pq->size - 1);
}

static unsigned char
pq_is_empty(struct prio_queue *pq)
{
	return (pq->size ? 0 : 1);
}

static void
pq_destroy(struct prio_queue *pq)
{
	if (pq->size_max) free(pq->array);
}

static void
pq_print(struct prio_queue *pq, char *delim)
{
	register int i = 0;

	for (i = 0; i < pq->size; i++)
		fprintf(stderr, "i=%5d: { a=%d b=%d weight=%lld }%s", i,
			pq->array[i].a, pq->array[i].b, pq->array[i].weight, delim);
	putchar('\n');
}
// }}}

int
time_machine(int a, const int a_len, const int k)
{
	int time = 0;

	while (heap__) {
	}
}

int
main(int argc, char **argv)
{
}
